/**
 * @version Create on 2012-11-1
 * @author Yinzi Chen
 */

public class DecodeWay {

	public int numDecodings(String s) {
		int n = s.length();
		int[] a = new int[n];
		for (int i = 0; i < n; ++i)
			a[i] = s.charAt(i) - '0';
		if (n == 0) {
			return 0;
		} else if (n == 1) {
			return a[0] != 0 ? 1 : 0;
		}
		int d[] = new int[n];
		d[0] = a[0] != 0 ? 1 : 0;
		d[1] = a[1] != 0 ? 1 : 0;
		if (a[0] != 0 && a[0] * 10 + a[1] < 27)
			d[1]++;
		if (d[0] == 0 || d[1] == 0)
			return 0;
		for (int i = 2; i < n; ++i) {
			if (a[i] != 0)
				d[i] += d[i - 1];
			if (a[i - 1] != 0 && a[i - 1] * 10 + a[i] < 27)
				d[i] += d[i - 2];
			if (d[i] == 0)
				return 0;
		}
		return d[n - 1];
	}

	public static void main(String[] args) {

	}

}
